package madixin.t503;

import java.util.Arrays;
import java.util.Stack;

class Solution {
        public int[] nextGreaterElements(int[] nums) {
            int[] result = new int[nums.length];
            Arrays.fill(result, -1);
            Stack<Integer> index = new Stack<Integer>();

            //需要循环2次
            for (int i = 0; i < nums.length * 2; i++) {
                int cur = nums[i % (nums.length)];
                while (!index.isEmpty() && nums[index.peek()] < cur) {
                    int pre = index.pop();
                    result[pre] = cur;
                }
                if (i < nums.length) {
                    index.push(i);
                }
            }
            return result;
        }

    public static void main(String[] args) {

        Solution s = new Solution();

        int res[] = s.nextGreaterElements(new int[]{1, 2, 1});

        Arrays.stream(res).forEach(x -> System.out.println(x));

    }

}